package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/3/15 16:49
 * @description：https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets/
 */
public class 统计按位或能得到最大值的子集数目 {
    @Test
    public void test() {
        Solution solution = new Solution();
        int[] nums = new int[16];
        for (int i = 0; i < 16; i++) {
            nums[i] = new Random().nextInt(35);
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(solution.countMaxOrSubsets(nums));
    }

    class Solution {
        int maxOrVal = Integer.MIN_VALUE;
        int count = 0;

        public int countMaxOrSubsets(int[] nums) {
            dfs(nums,0, 0);
            return count;
        }

        private void dfs(int[] nums, int idx, int orVal) {
            if (idx == nums.length) {
                if (orVal > maxOrVal) {
                    maxOrVal = orVal;
                    count = 1;
                } else if (orVal == maxOrVal) {
                    count++;
                }
                return;
            }
            // 拿
            dfs(nums, idx + 1, orVal | nums[idx]);
            // 不拿
            dfs(nums, idx + 1, orVal);
        }
    }
}
